// 1.冒泡排序

// 思路：

//  对未排序的各元素从头到尾依次比较相邻的两个元素大小关系
//  如果左边的队员高, 则两队员交换位置
//  向右移动一个位置, 比较下面两个队员
//  当走到最右端时, 最高的队员一定被放在了最右边
//  按照这个思路, 从最左端重新开始, 这次走到倒数第二个位置的队员即可.
//  依次类推, 就可以将数据排序完成

//  大 O 表示法

//  比较次数：O(N^2)
//  交换次数：O(N^2)
function bubbleSort(arr) {
  let length = arr.length;
  for (let i = length - 1; i >= 0; i--) {
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

// 2.选择排序

// 思路：

//  选定第一个索引位置，然后和后面元素依次比较
//  如果后面的队员, 小于第一个索引位置的队员, 则交换位置
//  经过一轮的比较后, 可以确定第一个位置是最小的
//  然后使用同样的方法把剩下的元素逐个比较即可
//  可以看出选择排序，第一轮会选出最小值，第二轮会选出第二小的值，直到最后

//  大 O 表示法

//  比较次数：O(N^2)
//  交换次数：O(N)
function selectionSort(arr) {
  let length = arr.length;
  for (let i = 0; i < length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}

// 3.插入排序

// 思路：

//  从第一个元素开始，该元素可以认为已经被排序
//  取出下一个元素 temp，在已经排序的元素序列中从后向前扫描
//  如果该元素（已排序的元素）大于新元素 temp，将该元素移到下一位置
//  重复上一个步骤，直到找到已排序的元素小于或者等于新元素 temp 的位置
//  将新元素插入到该位置后, 重复上面的步骤

// 插入排序的比较次数:

//  第一趟时, 需要的最多次数是 1, 第二趟最多次数是 2, 依次类推, 最后一趟是 N-1 次.
//  因此是 1 + 2 + 3 + ... + N - 1 = N \* (N - 1) / 2.
//  然而每趟发现插入点之前, 平均只有全体数据项的一半需要进行比较.
//  我们可以除以 2 得到 N \* (N - 1) / 4. 所以相对于选择排序, 插入排序的比较次数是少了一半的.

//  大 O 表示法

//  比较次数：O(N^2)
//  交换次数：O(N)
function insertionSort(arr) {
  let length = arr.length;
  for (let i = 1; i < length; i++) {
    let j = i;
    let temp = arr[i]; //当前值
    while (j > 0 && arr[j - 1] > temp) {
      arr[j] = arr[j - 1];
      j--;
    }
    [temp, arr[j]] = [arr[j], temp];
  }
  return arr;
}

// 4.希尔排序

// 思路：

//  比如下面的数字, 81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15.
//  我们先让间隔为 5, 进行排序. (35, 81), (94, 17), (11, 95), (96, 28), (12, 58), (35, 41), (17, 75), (95, 15)
//  排序后的新序列, 一定可以让数字离自己的正确位置更近一步.
//  我们再让间隔位 3, 进行排序. (35, 28, 75, 58, 95), (17, 12, 15, 81), (11, 41, 96, 94)
//  排序后的新序列, 一定可以让数字离自己的正确位置又近了一步.
//  最后, 我们让间隔为 1, 也就是正确的插入排序. 这个时候数字都离自己的位置更近, 那么需要复制的次数一定会减少很多.

// 选择合适的增量:

//  在希尔排序的原稿中, 他建议的初始间距是 N / 2, 简单的把每趟排序分成两半.
//  也就是说, 对于 N = 100 的数组, 增量间隔序列为: 50, 25, 12, 6, 3, 1.
//  这个方法的好处是不需要在开始排序前为找合适的增量而进行任何的计算.
//  我们先按照这个增量来实现我们的代码.
function shellSort(arr) {
  let length = arr.length;
  let gap = Math.floor(length / 2); //增量
  while (gap > 0) {
    // 插入排序
    for (let i = gap; i < length; i++) {
      // 保存临时变量
      let j = i;
      let temp = arr[i];
      while (j > gap - 1 && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
    gap = Math.floor(gap / 2); //更新增量
  }
  return arr;
}

// 5.快速排序

// 1.取基准值为数组最左边的数
function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return;
  let baseId = left,
    baseVal = arr[baseId],
    i = left,
    j = right;
  while (i < j) {
    while (j > i && arr[j] >= baseVal) {
      j--;
    }
    while (i < j && arr[i] <= baseVal) {
      i++;
    }
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  [arr[baseId], arr[i]] = [arr[i], arr[baseId]];
  quickSort(arr, left, i - 1);
  quickSort(arr, i + 1, right);
  return arr;
}
// 2.取基准值为数组最右边的数
function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return; // 如果左边的索引大于等于右边的索引说明整理完毕
  let baseVal = arr[right], // 取无序数组最后一个数为基准值
    i = left,
    j = right;
  while (i < j) {
    // 把所有比基准值小的数放在左边，比基准值大的数放在右边
    while (i < j && arr[i] < baseVal) {
      // 找到一个比基准值大的数交换
      i++;
    }
    arr[j] = arr[i]; // 将较大的值放在右边如果没有比基准值大的数就是将自己赋值给自己（i 等于 j）
    while (j > i && arr[j] > baseVal) {
      // 找到一个比基准值小的数交换
      j--;
    }
    arr[i] = arr[j]; // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i 等于 j）
  }
  arr[i] = baseVal; // 将基准值放至中央位置完成一次循环（这时候 j 等于 i ）
  quickSort(arr, left, i - 1); // 将左边的无序数组重复上面的操作
  quickSort(arr, i + 1, right); // 将右边的无序数组重复上面的操作
  return arr;
}
// 3.取基准值为数组最中间的数
// 实现1
function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return;
  let mid = arr[parseInt((left + right) / 2)], //枢纽选择的是中间的
    l = left,
    r = right;
  while (true) {
    while (arr[l] < mid) {
      l++;
    }
    while (arr[r] > mid) {
      r--;
    }
    if (l >= r) {
      break;
    }
    [arr[l], arr[r]] = [arr[r], arr[l]];
  }
  quickSort(arr, left, l - 1);
  quickSort(arr, l + 1, right);
  return arr;
}
// 实现2
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  let pivotIndex = Math.floor(arr.length / 2);
  let pivot = arr.splice(pivotIndex, 1)[0];
  let left = [];
  let right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

// 6.归并排序

// 算法步骤：

// 1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
// 2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
// 3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
// 4. 重复步骤 3 直到某一指针达到序列尾；
// 5. 将另一序列剩下的所有元素直接复制到合并序列尾。
function mergeSort(arr) {
  // 采用自上而下的递归方法
  let len = arr.length;
  if (len < 2) {
    return arr;
  }
  let middle = Math.floor(len / 2),
    left = arr.slice(0, middle),
    right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];

  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) result.push(left.shift());
  while (right.length) result.push(right.shift());
  return result;
}

// 7.堆排序

// 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；

// 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
// 总结下堆排序的基本思路：

// - 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
// - 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
// - 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

// 堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。

// 将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。

// 如此反复执行，便能得到一个有序序列了

// 堆排序是一种不稳定的排序方法
let dat = [5, 8, 10, 3, 2, 18, 17, 9];
//生成大顶堆
function adjustHeap(arr, i, len) {
  //将当前值保存
  let temp = arr[i];
  //从i结点的左子结点开始，也就是2i+1处开始
  for (let j = 2 * i + 1; j < len; j = 2 * j + 1) {
    //如果左子结点小于右子结点，j指向右子结点
    if (j + 1 < len && arr[j] < arr[j + 1]) {
      j++;
    }
    //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）值和索引都赋值
    if (arr[j] > temp) {
      arr[i] = arr[j];
      i = j;
    } else {
      break;
    }
  }
  arr[i] = temp; //将temp值放到最终的位置
}
function heapSort(data) {
  //构造大顶堆
  //此时我们从最后一个非叶子结点开始,叶结点自然不用调整
  ////从第一个非叶子结点从下至上，从右至左调整结构
  for (let i = data.length / 2 - 1; i >= 0; i--) {
    adjustHeap(data, i, data.length);
  }
  // console.log(data);
  //交换堆顶元素与末尾元素；不算最后一个元素，重新调整堆
  for (let k = data.length - 1; k > 0; k--) {
    //将堆顶元素与末尾元素进行交换
    [data[0], data[k]] = [data[k], data[0]];
    // console.log(data);
    //不算最后一个元素，重新对堆进行调整
    adjustHeap(data, 0, k);
  }
  return data;
}

let sortedData = heapSort(dat);
console.log(sortedData);

// TOPK问题 - 堆排

// 一般TOPK问题

// 时间复杂度：遍历数组需要 O(n) 的时间复杂度，一次堆化需要 O(logk) 时间复杂度，所以利用堆求 Top k 问题的时间复杂度为 O(nlogk)
// 空间复杂度：O(n)
// 小顶堆
function adjustHeap(arr, i, len) {
  for (let j = 2 * i + 1; j < len; j = 2 * j + 1) {
    if (j + 1 < len && arr[j] > arr[j + 1]) {
      j++;
    }
    if (arr[j] < arr[i]) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i = j;
    } else {
      break;
    }
  }
}

function topK(arr, k) {
  let a = arr.splice(0, k);
  for (let i = (k - 1) >> 1; i >= 0; i--) {
    adjustHeap(a, i, a.length);
  }
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > a[0]) {
      a[0] = arr[i];
      adjustHeap(a, 0, k);
    }
  }
  return a[0];
}

console.log(topK([1, 2, 3, 5, 6, 7], 4)); // 3

// 最长连续等于target的子序列

// - 滑动窗口

// > 时间复杂度：O(N)
function solution(arr, target) {
  let i = 0;
  let j = 0;
  let sum = arr[0];
  while (i <= j && i < arr.length - 1) {
    if (sum === target) {
      return arr.slice(i, j + 1);
    } else if (sum < target) {
      sum += arr[++j];
    } else {
      sum -= arr[i++];
    }
  }
  return false;
}

console.log(solution([3, 2, 1, 5, 4, 3, 7, 9], 12));
